package unionfindset;

import java.util.Arrays;

/**
 * @ClassName UnionFindSet
 * @Description 并查集
 * @Author ZJX
 * @Date 2024/9/7 19:16
 * @Version 1.0
 */
public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];

//        初始化每个元素的值都为-1
        Arrays.fill(elem,-1);
    }

    /**
     * 查找数据 x 的根节点
     * @param x
     * @return 下标
     */
    public int findRoot(int x) {
        if (x < 0){
            throw new IndexOutOfBoundsException("下标不合法，是负数");
        }

        // 如果当前节点不是根节点，继续递归查找
        if (elem[x] >= 0) {
            // 路径压缩：将当前节点直接指向根节点
            elem[x] = findRoot(elem[x]);
        }

        return x;
    }

    /*
     * @param x1:
    	 * @param x2:
      * @return boolean
     * @author: ZJX
     * @description: 查询x1 和 x2 是不是同一个集合
     * @date: 2024/9/7 20:27
     */
    public boolean isSameUnionFindSet(int x1,int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);

        return index1 == index2;
    }

    /*
     * @param x1:
    	 * @param x2:
      * @return void
     * @author: ZJX
     * @description: 并查集 合并 合并的都是根节点
     * @date: 2024/9/7 20:52
     */
    public void union(int x1,int x2) {
        int root1 = findRoot(x1);
        int root2 = findRoot(x2);

        if (root2 == root1){
            return ; // 两个根节点一样 无需合并
        }
        // 按秩合并：将元素少的集合合并到元素多的集合
        if (Math.abs(elem[root1]) >= Math.abs(elem[root2])){
//            root1的集合元素多 将root2集合合并到root1中
            elem[root1] += elem[root2];  // 更新 root1 的集合大小
            elem[root2] = root1;  // 将 root2 的父节点指向 root1
        } else {
            elem[root2] += elem[root1]; // 更新 root2 的集合大小
            elem[root1] = root2;  // 将 root1 的父节点指向 root2
        }
    }

    /*
     * @param :
      * @return int
     * @author: ZJX
     * @description:  计算并查集中有多少个独立集合
     * @date: 2024/9/7 21:18
     */
    public int getCount() {
        int count = 0;
        for (int x : elem){
           if (x < 0){
               count++;
           }
        }
        return count;
    }

    public void print() {
        for (int x : elem) {
            System.out.print(x+" ");
        }
        System.out.println();
    }

    /*
     * @param isConnected:
      * @return int
     * @author: ZJX
     * @description: 力扣 547 省份数量
     * @date: 2024/9/7 21:27
     */
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;  // 获取城市的数量（n * n 矩阵）

        // 初始化并查集，城市数量为 n
        UnionFindSet ufs = new UnionFindSet(n);

        // 遍历矩阵的所有元素
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {  // 只遍历上三角矩阵，避免重复
                if (isConnected[i][j] == 1) {
                    // 如果城市 i 和城市 j 直接相连，则将它们合并到同一个集合
                    ufs.union(i, j);
                }
            }
        }

        // 通过 getCount() 返回独立集合的数量，即省份的数量
        return ufs.getCount();
    }


    /*
     * @param equations: 字符串数组，表示等式和不等式
     * @return boolean: 是否所有的等式和不等式可以满足
     * @author: ZJX
     * @description: 力扣 990 等式方程的可满足性
     * @date: 2024/9/7 21:52
     */
    public boolean equationsPossible(String[] equations) {
        // 并查集初始化，包含 26 个字母
        UnionFindSet ufs = new UnionFindSet(26);

        // 第一遍处理等式 (==)，将所有相等的字符合并到同一个集合
        for (String equation : equations) {
            if (equation.charAt(1) == '=') { // 等式 "=="
                int x = equation.charAt(0) - 'a'; // 第一个字母
                int y = equation.charAt(3) - 'a'; // 第二个字母
                ufs.union(x, y); // 将两个字母合并
            }
        }

        // 第二遍处理不等式 (!=) 检查是否有矛盾
        for (String equation : equations) {
            if (equation.charAt(1) == '!') { // 不等式 "!="
                int x = equation.charAt(0) - 'a'; // 第一个字母
                int y = equation.charAt(3) - 'a'; // 第二个字母
                // 如果不等式两边的变量在同一个集合中，说明矛盾，返回 false
                if (ufs.findRoot(x) == ufs.findRoot(y)) {
                    return false;
                }
            }
        }

        // 如果没有冲突，返回 true
        return true;
    }

}
